/*
 * @lc app=leetcode.cn id=560 lang=cpp
 * @lcpr version=30204
 *
 * [560] 和为 K 的子数组
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution
{
public:
    int subarraySum(vector<int> &nums, int k)
    {
        unordered_map<int, int> prefixCount; // 存储前缀和出现的次数
        prefixCount[0] = 1;                  // 初始化前缀和为 0 的次数为 1
        int prefixSum = 0;                   // 当前的前缀和
        int count = 0;                       // 子数组的数量

        for (int num : nums)
        {
            prefixSum += num; // 更新当前前缀和
            // 检查是否存在 prefixSum - k
            if (prefixCount.find(prefixSum - k) != prefixCount.end())
            {
                count += prefixCount[prefixSum - k];
            }
            // 更新当前前缀和的出现次数
            prefixCount[prefixSum]++;
        }

        return count;
    }
};
// @lc code=end

/*
// @lcpr case=start
// [1,1,1]\n2\n
// @lcpr case=end

// @lcpr case=start
// [1,2,3]\n3\n
// @lcpr case=end

 */
